라흐 수

1. 개요2. 정의3. 성질

3.1. 점화식3.2. 일반항

4. 관련 문서

Lah number

1. 개요 [편집]

라흐 수는 1954년에 슬로베니아의 수학자 이보 라흐(Ivo Lah)에 의해 정의된 수로서,

L(n,\,k)

로 표기된다. 표기가 표기이다보니 ‘라 수’로도 알려져 있다.[1]제1종 스털링 수, 제2종 스털링 수와 밀접한 관련이 있는 점으로부터 드물게 ‘제3종 스털링 수’라고도 불린다.[2] 제1종 스털링 수처럼, 부호 없는 라흐 수

L(n,\,k)

와 부호 있는 라흐 수

L'(n,\,k) = (-1)^{n-k} L(n,\,k)

로 나뉜다.[3]

0 \le k \le n \le 10

범위에서[4]

L(n,\,k)

값은 다음과 같다. 아래 테이블에서 배경이 어두운 칸은

L'(n,\,k)

의 부호가

(-)

임을 의미한다.

$n \Big\backslash k$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$0$	$1$	$0$
$1$	$0$	$1$	$0$
$2$		$2$	$1$	$0$
$3$		$6$	$6$	$1$	$0$
$4$		$24$	$36$	$12$	$1$	$0$
$5$		$120$	$240$	$120$	$20$	$1$	$0$
$6$		$720$	$1800$	$1200$	$300$	$30$	$1$	$0$
$7$		$5040$	$15120$	$12600$	$4200$	$630$	$42$	$1$	$0$
$8$		$40320$	$141120$	$141120$	$58800$	$11760$	$1176$	$56$	$1$	$0$
$9$		$362880$	$1451520$	$1693440$	$846720$	$211680$	$28224$	$2016$	$72$	$1$	$0$
$10$		$3628800$	$16329600$	$21772800$	$12700800$	$3810240$	$635040$	$60480$	$3240$	$90$	$1$

2. 정의 [편집]

라흐 수는 상승 계승 식을 하강 계승의 합으로 나타냈을 때 하강 계승에 곱해지는 계수로 정의된다.

\displaystyle x^{\overline n} = \sum_{k=0}^n L(n,\,k) x^{\underline k}

k=1

부터 더하는 경우가 일반적인데,

x^{\overline 0} = x^{\underline 0} = 1

이고

L(0,\,k) = \delta_{0,\,k}

(

\delta_{0,\,k}

는 크로네커 델타)이므로

n=0

일 때도 문제없이 위 식이 성립한다.

n \ge 1

이면 양변에 상수항이 없으므로 당연히

L(n,\,0) = \delta_{n,\,0}

도 만족한다.
부호 없는 제1종 스털링 수

\begin{bmatrix} n \\ r \end{bmatrix}

, 제2종 스털링 수

\begin{Bmatrix} r \\ k \end{Bmatrix}

가 각각

\displaystyle x^{\overline n} = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} x^r

,

\displaystyle x^r = \sum_{k=0}^r \begin{Bmatrix} r \\ k \end{Bmatrix} x^{\underline k}

를 만족하므로 위 식에 대입하면

\displaystyle \begin{aligned} x^{\overline n} &= \sum_{k=0}^n L(n,\,k) x^{\underline k} = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} x^r = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} \sum_{k=0}^r \begin{Bmatrix} r \\ k \end{Bmatrix} x^{\underline k} \\ &= \sum_{k=0}^n \left( \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} \right) x^{\underline k} \end{aligned}

즉

\displaystyle L(n,\,k) = \sum_{r=0}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix}

인데

r<k

이면

\begin{Bmatrix} r \\ k \end{Bmatrix} = 0

이므로 다음과 같이 간략하게 나타낼 수 있다. 라흐 수가 ‘제3종 스털링 수’라고도 불리는 이유를 극명하게 보여주는 성질이기도 하다.

\displaystyle L(n,\,k) = \sum_{r=k}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix}

스털링 수와 마찬가지로, 집합론을 이용해서 정의할 수도 있다. 라흐 수는

n

개의 원소를 구분되지 않는

k

개의 순열로 분할하는 경우의 수로 정의된다. 역시 각 정의에 입각해서 점화식을 써보면 똑같은 꼴이 유도된다.

라흐 수의 정의식에서

x

에

-x

를 대입하면

(-x)^{\overline n} = (-1)^n x^{\underline n}

,

(-x)^{\underline k} = (-1)^k x^{\overline k}

이므로

\displaystyle (-x)^{\overline n} = (-1)^n x^{\underline n} = \sum_{k=0}^n L(n,\,k) (-x)^{\underline k} = \sum_{k=0}^n L(n,\,k) (-1)^k x^{\overline k} \\ \begin{aligned} x^{\underline n} &= \sum_{k=0}^n (-1)^{k-n} L(n,\,k) x^{\overline k} \\ \therefore x^{\underline n} &= \sum_{k=0}^n (-1)^{n-k} L(n,\,k) x^{\overline k} \end{aligned}

즉, 상승 계승과 하강 계승을 서로 맞바꿔주면 라흐 수에

(-1)^{n-k}

이 곱해지는 꼴이 되는데

(-1)^{n-k} L(n,\,k)

를 부호 있는(signed) 라흐 수라고도 하며

L'(n,\,k)

등으로 나타낸다.[5]

3. 성질 [편집]

3.1. 점화식 [편집]

L(n+1,\,k) = L(n,\,k-1) +(n+k) L(n,\,k)

스털링 수를 이용하여 나타낸 표기를 이용하면 간단하게 증명이 가능하다. 부호 없는 제1종 스털링 수, 제2종 스털링 수의 점화식이 각각

\begin{bmatrix} n+1 \\ r \end{bmatrix} = \begin{bmatrix} n \\ r-1 \end{bmatrix} + n \begin{bmatrix} n \\ r \end{bmatrix}

,

\begin{Bmatrix} r \\ k \end{Bmatrix} = \begin{Bmatrix} r-1 \\ k-1 \end{Bmatrix} + k \begin{Bmatrix} r-1 \\ k \end{Bmatrix}

로 주어지므로 대입하면

\displaystyle \begin{aligned} L(n+1,\,k) &= \sum_{r=k}^{n+1} \begin{bmatrix} n+1 \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} = \sum_{r=k}^{n+1} \left( \begin{bmatrix} n \\ r-1 \end{bmatrix} + n \begin{bmatrix} n \\ r \end{bmatrix} \right) \begin{Bmatrix} r \\ k \end{Bmatrix} = \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} + n \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} \\ &= \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \left( \begin{Bmatrix} r-1 \\ k-1 \end{Bmatrix} + k \begin{Bmatrix} r-1 \\ k \end{Bmatrix} \right) + n \sum_{r=k}^n \begin{bmatrix} n \\ r \end{bmatrix} \begin{Bmatrix} r \\ k \end{Bmatrix} \\ &= \sum_{r=k}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \begin{Bmatrix} r-1 \\ k-1 \end{Bmatrix} + k \sum_{r=k+1}^{n+1} \begin{bmatrix} n \\ r-1 \end{bmatrix} \begin{Bmatrix} r-1 \\ k \end{Bmatrix} + n L(n,\,k) \\ &= L(n,\,k-1) + k L(n,\,k) + n L(n,\,k) \\ &= L(n,\,k-1) + (n+k) L(n,\,k) \end{aligned}

집합론을 이용해서도 증명할 수 있다.

(n+1)

번째 원소를 추가하여

k

개의 순열로 만들 때 크게 두 가지 경우로 나눌 수 있다. 첫 번째는

(n+1)

번째 원소를 길이가

1

인 순열로 추가하는 경우, 두 번째는 기존

n

개 원소를

k

개 순열로 분할한 것에

(n+1)

번째 원소를 끼워넣는 경우이다. 전자는

n

개 원소를

(k-1)

개 순열로 분할한 경우의 수

L(n,\,k-1)

가 그대로 쓰인다. 후자는 각 순열 집합에서 원소의 맨 앞, 사이사이, 맨 뒤를 모두 세어준 값을

L(n,\,k)

에 곱하면 되는데,

k

개의 순열 집합을 일렬로 쭉 늘어놓고 세어보면 총 원소의 맨 앞, 사이사이, 맨 뒤의 수

(n+1)

와 각 분할을 나누는 경계의 수

(k-1)

를 한 번 더 세어준 값

(n+1)+(k-1)=n+k

와 같다는 것을 알 수 있다. 정리하면 위 식이 얻어진다.

L(n,\,k+1) = \dfrac{n-k}{k(k+1)} L(n,\,k)

집합론을 이용해서 유도할 수 있다. 먼저 ‘공집합 없이 구분되지 않는 부분 집합

k

개로 분할한다’를

(k-1)

개의 칸막이를 끼워넣는 조작’으로 바꿔 해석하면,

k \to k+1

이란 곧 칸막이를 하나 늘리는 것으로 이해할 수 있다.

L(n,\,k)

에서 각 순열 집합을 일렬로 쭉 늘어놓고 공집합이 없이 새 칸막이를 끼워넣을 수 있는 자리의 수를 따져보면, 모든 원소의 사이인

(n-1)

에서 칸막이의 개수

(k-1)

개를 뺀

(n-k)

이므로

(k+1)

개로 분할한 경우의 수는

(n-k) L(n,\,k)

가 된다. 그런데 다음과 같이 새 칸막이를 끼움으로써 중복이 생기는 경우가 있다. 예를 들어 3개 → 4개로 순열 분할을 늘릴 때

\begin{cases} \begin{aligned} \begin{pmatrix} a & b & c \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} f & g & h \end{pmatrix} &\to \begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} f & g & h \end{pmatrix} \\ \begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & b & f & g & h \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix} &\to \begin{pmatrix} c \end{pmatrix},\,\begin{pmatrix} a & b \end{pmatrix}, \begin{pmatrix} f & g & h \end{pmatrix},\,\begin{pmatrix} d & e \end{pmatrix} \\ \begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} f & g & h & c \end{pmatrix} &\to \begin{pmatrix} d & e \end{pmatrix},\,\begin{pmatrix} a & b \end{pmatrix},\,\begin{pmatrix} f & g & h \end{pmatrix}, \begin{pmatrix} c \end{pmatrix} \\ &\vdots \\ &\vdots \end{aligned} \end{cases}

와 같이, 분할 전의 경우의 수는 서로 다르지만 분할 후 중복되게 된다. 이 경우의 수는 분할 후의 순열 두 개를 결합시켜서 분할 전 상태를 만드는 경우의 수로 따져보면 되는데

(k+1)

개의 순열 집합에서

2

개를 골라내어 배열하는 경우의 수

{}_{k+1}\mathrm P_2 = k(k+1)

와 같으므로 이 값으로 나누어주면 된다. 따라서

L(n,\,k+1) = \dfrac{n-k}{k(k+1)} L(n,\,k)

3.2. 일반항 [편집]

L(n,\,k) = \dbinom nk \dfrac{(n+1)!}{(k+1)!} = \dbinom{n+1}{k+1} \dfrac{n!}{k!}

점화식 항목의 두 번째 식을 이용하면 된다.

\begin{aligned} L(n,\,k+1) &= \dfrac{n-k}{k \cdot (k+1)} L(n,\,k) = \dfrac{(n-k)(n-k+1) }{ k(k-1) \cdot (k+1) k} L(n,\,k-1) \\ &= \frac{(n-k)(n-k+1)(n-k+2) }{ k(k-1)(k-2) \cdot (k+1) k(k-1)} L(n,\,k-2) = \cdots\cdots = \dfrac{\displaystyle \prod_{i=1}^k(n-i)}{ k!(k+1)! } L(n,\,1) \\ &= \dfrac{(n-1)!}{k!(k+1)!(n-k-1)!} L(n,\,1) \end{aligned}

L(n,\,1)

은

n

개의 원소를

1

개의 순열로 나타내는 경우이므로

L(n,\,1) = n!

이다. 따라서

\begin{aligned} L(n,\,k+1) &= \dfrac{(n-1)!n!}{k!(n-k-1)!(k+1)!} = \dbinom{n-1}k \dfrac{n!}{(k+1)!} = \dbinom n{k+1} \dfrac{(n-1)!}{k!} \\ L(n,\,k) &= \dbinom{n-1}{k-1} \dfrac{n!}{k!} = \dbinom nk \dfrac{(n+1)!}{(k+1)!}\,(1 \le k \le n) \\ \therefore L(n,\,k) &= \dbinom nk \dfrac{(n+1)!}{(k+1)!} = \dbinom{n+1}{k+1} \dfrac{n!}{k!}\,(0 \le k \le n) \end{aligned}

참고로 스털링 수의 경우처럼

n<k

이면 이항계수가 정의되지 않으나 편의상

L(n,\,k) = 0

으로 정의한다.

4. 관련 문서 [편집]

[1] 한국어판 위키피디아에는 ‘라 수’로 등재되어있는데 슬로베니아어에서 h는 무성 연구개 마찰음 /x/ 음가이기 때문에 바흐(Bach)의 ch처럼 ‘라흐’로 표기하는 게 맞는다.[2] 각 스털링 수의 정의를 이용해서 식을 세우다보면 튀어나온다. 후술[3] 인지도가 낮아서인지 실례는 많지 않으나 부호 있는 라흐 수를

L(n,\,k)

로 나타내고 부호 없는 라흐 수를

|L(n,\,k)| = \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor

로 표기하는 경우도 있다.[4]

n<k

이면 조합론 수준에서는 정의되지 않으나 대수적으로도 정의된다는 점 때문에

0

인 것으로 약속한다.[5]

L(n,\,k)

표기에 대해선 정반대를 의미하는 경우도 있다. 프랑스어 버전 위키피디아의 라흐 수 페이지에서는 제1종 스털링 수처럼 부호 있는 라흐 수를

L(n,\,k)

로, 부호 없는 라흐 수를

|L(n,\,k)| = \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor

로 나타낸다.